package com.heima.leetcode.practice;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 239 滑动窗口最大值
 * @date 2024/11/18 16:25
 */
public class E239 {

    /**
     * <h3>方法一：暴力解题，会超出时间限制</h3>
     *
     * @param nums 数组
     * @param k    滑动窗口大小
     * @return 最大值数组
     */
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int i = 0, j, max = 0;
        int[] result = new int[nums.length - k + 1];
        if (nums.length < k) j = nums.length - 1;
        else j = k - 1;
        while (j <= nums.length - 1) {
            max = nums[i];
            for (int m = i + 1; m <= j; m++) {
                if (nums[m] > max) max = nums[m];
            }
            result[i] = max;
            i++;
            j++;
        }
        return result;
    }

    /**
     * <h3>方法二：用类似于记忆法的方式优化方法一</h3>
     *
     * @param nums 数组
     * @param k    滑动窗口大小
     * @return 最大值数组
     */
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int i = 0, j, max = 0;
        int[] result = new int[nums.length - k + 1];
        if (nums.length < k) j = nums.length - 1;
        else j = k - 1;
        while (j <= nums.length - 1) {
            max = nums[i];
            if (i == 0) {
                for (int m = i + 1; m <= j; m++)
                    if (nums[m] > max) max = nums[m];
            } else {
                if (result[i - 1] != nums[i - 1]) {
                    max = Math.max(result[i - 1], nums[j]);
                } else {
                    max = nums[i];
                    for (int m = i + 1; m <= j; m++)
                        if (nums[m] > max) max = nums[m];
                }
            }
            result[i] = max;
            i++;
            j++;
        }
        return result;
    }

    /**
     * <h3>方法三：使用单调队列</h3>
     *
     * @param nums 数组
     * @param k    滑动窗口大小
     * @return 最大值数组
     */
    public int[] maxSlidingWindow3(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        MonotonicQueue<Integer> queue = new MonotonicQueue<>();
        for (int i = 0; i < nums.length; i++) {
            // 当前队列中最大值如果不是滑动窗口范围的元素，移除
            if (!queue.isEmpty() && i - k >= 0 && queue.peek() == nums[i - k]) {
                queue.poll();
            }
            // 添加元素
            queue.offer(nums[i]);
            // i > k - 1则添加到结果数组中
            if (i >= k - 1) {
                result[i - k + 1] = queue.peek();
            }
        }
        return result;
    }

    /**
     * 简略实现的单调队列，默认是单调递减的思路
     *
     * @param <E> 元素类型
     */
    static class MonotonicQueue<E extends Comparable<E>> {
        private final LinkedList<E> deque;

        public MonotonicQueue() {
            deque = new LinkedList<>();
        }

        public E peek() {
            return deque.peekFirst();
        }

        public E poll() {
            return deque.pollFirst();
        }

        /**
         * 入队，把队列中比它大的移除
         *
         * @param e 元素
         */
        public void offer(E e) {
            while (!deque.isEmpty() && deque.peekLast().compareTo(e) < 0) {
                deque.pollLast();
            }
            deque.offerLast(e);
        }

        public boolean isEmpty() {
            return deque.isEmpty();
        }
    }

    /**
     * <h3>方法四：使用单调队列，直接用deque</h3>
     *
     * @param nums 数组
     * @param k    滑动窗口大小
     * @return 最大值数组
     */
    @SuppressWarnings("all")
    public int[] maxSlidingWindow4(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        LinkedList<Integer> deque = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            // 当前队列中最大值如果不是滑动窗口范围的元素，移除
            if (!deque.isEmpty() && i - k >= 0 && deque.peek() == nums[i - k]) {
                deque.pollFirst();
            }
            // 添加元素
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.pollLast();
            }
            deque.offerLast(nums[i]);
            // i > k - 1则添加到结果数组中
            if (i >= k - 1) {
                result[i - k + 1] = deque.peekFirst();
            }
        }
        return result;
    }

    /**
     * <h3>方法五：使用单调队列，直接用deque，存的是索引，推荐，好理解</h3>
     *
     * @param nums 数组
     * @param k    滑动窗口大小
     * @return 最大值数组
     */
    @SuppressWarnings("all")
    public int[] maxSlidingWindow5(int[] nums, int k) {
        // 1. 准备结果数组和单调队列
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        // 2. 遍历数组，加到单调队列中
        for (int i = 0; i < nums.length; i++) {
            // 2.1 如果队列中最大元素不是滑动窗口范围的元素，移除
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            // 2.2 添加元素并保证单调递减
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            // 2.3 如果i大于等于滑动窗口大小（滑动窗口已经形成），则添加到结果数组中
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}
